package exercises.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode-cn.com/problems/01-matrix/">
 * 542. 01 矩阵</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 * <p>
 * 两个相邻元素间的距离为 1 。
 * <p>
 * 提示：
 * <li>m == mat.length</li>
 * <li>n == mat[i].length</li>
 * <li>1 <= m, n <= 104</li>
 * <li>1 <= m * n <= 104</li>
 * <li>mat[i][j] is either 0 or 1.</li>
 * <li>mat 中至少有一个 0 </li>
 *
 * @author or2
 * @date 2021年09月27日 时间: 12:09
 */
public class No542 {
    /**
     * 广度搜索 - 队列
     *
     * @param mat 二维整型数组表示的地图
     * @return 算好距离的地图
     */
    public int[][] updateMatrix(int[][] mat) {
        int colLen = mat.length;
        int rowLen = mat[0].length;
        /*将 1 置为 10001, 防止语义混淆; ②: 为广度遍历准备*/
        Deque<int[]> queue = new LinkedList<>();
        for (int col = 0; col < colLen; col++)
            for (int row = 0; row < rowLen; row++)
                if (mat[col][row] == 1)
                    mat[col][row] = 10001;
                else
                    queue.add(new int[]{col, row});
        /*标识广度层数*/
        int[] last = queue.getLast();
        int size = 1;
        /*开始广度遍历*/
        while (!queue.isEmpty()) {
            /*取出坐标*/
            int[] first = queue.removeFirst();
            int col = first[0], row = first[1];
            /*判断四周 - 左右,上下*/
            if (row > 0 && mat[col][row - 1] > size) {
                mat[col][row - 1] = size;
                queue.add(new int[]{col, row - 1});
            }
            if (row < rowLen - 1 && mat[col][row + 1] > size) {
                mat[col][row + 1] = size;
                queue.add(new int[]{col, row + 1});
            }
            if (col > 0 && mat[col - 1][row] > size) {
                mat[col - 1][row] = size;
                queue.add(new int[]{col - 1, row});
            }
            if (col < colLen - 1 && mat[col + 1][row] > size) {
                mat[col + 1][row] = size;
                queue.add(new int[]{col + 1, row});
            }
            /*广度结束?*/
            if (first == last && !queue.isEmpty()) {
                last = queue.getLast();
                size++;
            }
        }

        return mat;
    }

    /**
     * 使用动态规划解决问题
     */
    public int[][] updateMatrixDP(int[][] mat) {
        int colLen = mat.length;
        int rowLen = mat[0].length;
        /*将 1 置为 10001, 防止语义混淆*/
        for (int col = 0; col < colLen; col++)
            for (int row = 0; row < rowLen; row++)
                if (mat[col][row] == 1)
                    mat[col][row] = 10001;

        /*第一行边界处理*/
        for (int row = 1; row < rowLen; row++)
            if (mat[0][row] != 0)
                mat[0][row] = mat[0][row - 1] + 1;
        /*左上↘右下动态规划*/
        for (int col = 1; col < colLen; col++) {
            if (mat[col][0] != 0)
                mat[col][0] = mat[col - 1][0] + 1;
            for (int row = 1; row < rowLen; row++)
                if (mat[col][row] != 0)
                    mat[col][row] = Math.min(mat[col - 1][row], mat[col][row - 1]) + 1;
        }

        /*倒数第一行边界处理*/
        for (int row = rowLen - 2; row >= 0; row--)
            if (mat[colLen - 1][row] != 0)
                if (mat[colLen - 1][row] > mat[colLen - 1][row + 1] + 1)
                    mat[colLen - 1][row] = mat[colLen - 1][row + 1] + 1;
        /*右下↖左上动态规划*/
        for (int col = colLen - 2; col >= 0; col--) {
            if (mat[col][rowLen - 1] != 0)
                /*此时该点已蕴含自 左、上 的最短路径, 判断留最小的*/
                if (mat[col][rowLen - 1] > mat[col + 1][rowLen - 1] + 1)
                    mat[col][rowLen - 1] = mat[col + 1][rowLen - 1] + 1;
            for (int row = rowLen - 2; row >= 0; row--)
                if (mat[col][row] != 0) {
                    int rightBelow = Math.min(mat[col + 1][row], mat[col][row + 1]) + 1;
                    mat[col][row] = Math.min(mat[col][row], rightBelow);
                }
        }

        return mat;
    }
}
